﻿#include <iostream>
#include <map>
//#include <set>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

//两个数组的交集
//https://leetcode.cn/problems/intersection-of-two-arrays/description/
//class Solution
//{
//public:
//    vector<int> intersection(vector<int>& nums1, vector<int>& nums2)
//    {
//        vector<int> v1;
//        set<int> s1(nums1.begin(), nums1.end());
//        set<int> s2(nums2.begin(), nums2.end());
//        for (auto& e : s1)
//        {
//            auto ret = s2.find(e);
//            if (ret != s2.end())
//            {
//                v1.push_back(e);
//            }
//        }
//        
//        return v1;
//    }
//};

//int main()
//{
//    vector<int> n1 = { 1, 2, 2, 1 } ;
//    vector<int> n2 = { 2, 2 };
//    Solution s;
//    vector<int> ret1 = s.intersection(n1, n2);
//
//    for (auto& e : ret1)
//    {
//        cout << e << " ";
//    }
//
//	return 0;
//}


//int main()
//{
//	//map<string, string> m1 = { {"left", "左边"}, {"right", "右边"}, {"insert", "插入"}, {"string", "字符串"} };
//	//for (auto& e : m1)
//	//{
//	//	cout << e.first << " " << e.second << endl;;
//	//}
//	return 0;
//}


//int main()
//{
	//string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜","苹果", "香蕉", "苹果", "香蕉" };
	map<string, int> m2;
	//for (auto& e : arr)
	//{
	//	map<string, int>::iterator it = m2.find(e);
	//	if (it == m2.end())
	//	{
	//		m2.insert({ e,1 });
	//	}
	//	else
	//	{
	//		++it->second;
	//	}
	//}

	//for (auto& e : arr)
	//{
	//	m2[e]++;
	//}


	//for (auto& e : m2)
	//{
	//	cout << e.first << " " << e.second << endl;
	//}

	//map<string, string> m3 = { {"left","左边"}, {"right","右边"}, {"insert", "插入"} };

	//修改
	//m3["left"] = "剩余的";
 //
	//for (auto& e : m3)
	//{
	//	cout << e.first << " " << e.second << endl;
	//}

	//插入+修改
	//m3["hello"] = "你好";

	//for (auto& e : m3)
	//{
	//	cout << e.first << " " << e.second << endl;
	//}

	//查找
//	cout << m3["left"] << endl; //key 对应的value
//
//	return 0;
//}

//链表是否带环
//https://leetcode.cn/problems/linked-list-cycle-ii/description/


//随机链表的复制
// https://leetcode.cn/problems/copy-list-with-random-pointer/description/
//class Node 
//{
//public:
//	int val;
//	Node* next;
//	Node* random;
//
//	Node(int _val) 
//	{
//		val = _val;
//		next = NULL;
//		random = NULL;
//	}
//};
//
//class Solution
//{
//public:
//	Node* copyRandomList(Node* head)
//	{
//		map<Node*, Node*> mp;
//		Node* newhead = nullptr;
//		Node* newtail = nullptr;
//		Node* prev = head;
//		while (prev)
//		{
//			if (newtail == nullptr)
//			{
//				newtail = new Node(prev->val);
//			}
//			else
//			{
//				newtail = new Node(prev->val);
//				newtail = newtail->next;
//			}
//
//			mp.insert({ prev, newtail });
//
//			prev = prev->next;
//		}
//
//		//由原来的结点，判断新结点的random
//		Node* cur = head;
//		Node* newnode = newhead;
//		while (cur)
//		{
//			if (cur->random == nullptr)
//			{
//				newnode->random = nullptr;
//			}
//			else
//			{
//				newnode->random = mp[cur->random];
//			}
//			cur = cur->next;
//			newnode = newnode->next;
//		}
//
//		return newhead;
//	}
//};


//int main()
//{
//	return 0;
//}


//前K个高频词
// https://leetcode.cn/problems/top-k-frequent-words/description/
// 注意按字典序输出
// 用 map 解决
//class Solution
//{
//public:
//	vector<string> topKFrequent(vector<string>& words, int k)
//	{
//		map<string, int> mp;
//		for (auto& e : words)
//		{
//			mp[e]++;
//		}
//
//		multimap<int, string,greater<int>> mp2;
//		//auto it = mp.begin();
//		//while (it != mp.end())
//		//{
//		//	mp2.insert({ it->second, it->first });
//		//}
//
//		for (auto& e : mp)
//		{
//			mp2.insert({ e.second, e.first });
//		}
//
//		vector<string> v1;
//		auto it = mp2.begin();
//		while (k--)
//		{
//			v1.push_back(it->second);
//			it++;
//		}
//
//		return v1;
//	}
//};

//用稳定的排序，归并排序
//class Solution
//{
//public:
//
//	class mpcmp
//	{
//	public:
//		bool operator()(const pair<string, int>& kv1 , const pair<string, int>& kv2)
//		{
//			return kv1.second > kv2.second;
//		}
//	};
//
//	vector<string> topKFrequent(vector<string>& words, int k)
//	{
//		map<string, int> mp;
//		for (auto& e : words)
//		{
//			mp[e]++;
//		}
//
//		vector<pair<string, int>> v1(mp.begin(), mp.end());
//		stable_sort(v1.begin(), v1.end(), mpcmp());
//		
//		vector<string> v2;
//		auto it = v1.begin();
//		while (k--)
//		{
//			v2.push_back(it->first);
//			++it;
//		}
//
//		return v2;
//	}
//};

//运用快排，实现字典序小的在前的仿函数

//class Solution
//{
//public:
//
//	class kvcmp
//	{
//	public:
//		bool operator()(pair< string, int> kv1, pair< string, int> kv2)
//		{
//			return (kv1.second > kv2.second) || (kv1.first < kv2.first && kv1.second == kv2.second);
//		}
//	};
//
//	vector<string> topKFrequent(vector<string>& words, int k)
//	{
//		map<string, int> mp;
//		for (auto& e : words)
//		{
//			mp[e]++;
//		}
//
//		vector <pair< string, int>> v1(mp.begin(), mp.end());
//		sort(v1.begin(), v1.end(), kvcmp());
//
//		vector<string> v2;
//		auto it = v1.begin();
//		while (k--)
//		{
//			v2.push_back(it->first);
//			it++;
//		}
//
//		return v2;
//	}
//};
//
//int main()
//{
//	vector<string> words = {"i", "love", "leetcode", "i", "love", "coding"};
//	int k = 2;
//
//	Solution s;
//	vector<string> v1 = s.topKFrequent(words, k);
//
//	for (auto& e : v1)
//	{
//		cout << e << " ";
//	}
//
//	return 0;
//}


//int main()
//{
//	priority_queue<int> pq;
//	pq.push(3);
//	pq.push(1);
//	pq.push(5);
//	pq.push(0);
//
//	while(!pq.empty())
//	{
//		cout << pq.top() << " ";
//		pq.pop();
//	}
//
//	return 0;
//}

//int func(int n)
//{
//	if (n == 1 || n ==0 )
//	{
//		return n;
//	}
//	return func(n - 1) + func(n - 2);
//}
//
//int main()
//{
//	int x = 0;
//	cin >> x;
//	int ret = func(x);
//	cout << ret << endl;
//
//	return 0;
//}